package 回溯;
import org.junit.Test;

import java.util.List;
import java.util.ArrayList;
import java.util.Deque;
import java.util.ArrayDeque;
public class leetcode51N皇后 {	
	public static void main(String []args) {
//		System.out.println(NQueen(14));
		System.out.println(solution(4));
	}
	/**
	 * 只要思想不滑坡  方法 总比 困难多
	 * 不能在 同一行 同一列 同一对角线
	 */
	public static List<List<String>> solution(int n){
		if(n<1) {
			return null;
		}
//		List<List<String>> ans=new ArrayList<>(n);
//		Deque<String> path  = new ArrayDeque<>(n);
		int arr[] = new int [n];
		// 我靠 这他妈 都可以 我靠
//		String [] path =new String[n];
//		List<String[]> ans =new ArrayList<>();
		char[][] path =new char[n][n];
		for(int i=0;i < n;i++) {
			for(int j=0;j < n;j++ ) {
				path[i][j]='.';
			}
		}
		List<List<String>> ans=new ArrayList<>(n);
		process(0,n,path,ans,arr);
		return ans;
	}
	public static void process(int index,int n,char[][] path,
			List<List<String>> ans,int arr[]) {
		if(index==n) {
			ans.add(asList(path));
			return ;
		}
		for(int i=0;i < n; i++) {
			if(isValid(i,index,arr)) {
//				path.add("Q");
				path[index][i] = 'Q';
				arr[index]=i;
				process(index+1,n,path,ans,arr);
				path[index][i] = '.';
//				path.removeLast(); // 放在这个位置 行不行？
			}
//			else {
////				path.add(".");
////				process() 
//			}
//			path.removeLast();
		}
	}
	public static List<String> asList(char[][] path){
		List<String> list=new ArrayList<>();
		for(int i=0;i < path.length;i++) {
			list.add(String.valueOf(path[i]));
		}
		return list;
	}
	public static int NQueen(int n) {
		/** 注意这个数组 就是 这个 N皇后  在数组中的坐标
		 * 数组的下 标 代表的 是  行 index 就是行
			数组中的值的 表示的是列  arr[index] 就是 列
			这个 二维表  无论无何 都是 省不掉的  关键是用那种形式表示的 二维表最 省空间
		 */
		if(n < 1) {
			return 0;
		}
		int arr[] = new int [n];
		
		return process(n,0,arr);
	}
	public static int process(int n,int index,int arr[]) {
		if(index==n) {
			return 1;
			// 既然到达这个位置 说明 找到了一种方法
		}
		int ways=0;
		for(int i=0;i < n;i++) {
//			arr[index]=i;   这样写 是 有问题的 应该判断之后 在 添加到 表中
			if(isValid(i,index,arr)) {
				arr[index] =i;
				ways+=process(n,index+1,arr);
			}
		}
		return ways;
	}
	public static boolean isValid(int i,int index,int arr[]) {
//		if(index==0) {
//			return true;
//		}
//		if((i==arr[index-1]) ||  Math.abs()) {
//			
//			return false;
//		}
		for(int j=0;j < index;j++) {
			// 从第 一行 开始 比对 “当前的列 ” 有 没 有 与前面的 某一行的 列 相同  或者 在对角线上
			if(i==arr[j] || (Math.abs(i-arr[j]) == Math.abs(index-j))) {
				return false;
			}
		}
		return true;
	}
	@Test
	public void test(){
		System.out.println('a' - 32);
	}
		
}
